import java.util.Arrays;

/**
* @description: 698. 划分为k个相等的子集
* @author hewei
* @date 2022/8/11 14:31
* @version 1.0
*/

public class CanPartitionKSubsets {

    public static void main(String[] args) {
        CanPartitionKSubsets canPartitionKSubsets = new CanPartitionKSubsets();
        int[] nums = {1,1,1,1,2,2,2,2};
        System.out.println(canPartitionKSubsets.canPartitionKSubsets(nums, 4));
    }

    int[] kids;
    public boolean canPartitionKSubsets(int[] nums, int k) {
        kids = new int[k];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        int target = sum / k;
        if (target * k != sum) return false;
        Arrays.sort(nums);
        return process(target, nums, nums.length - 1);
    }

    public boolean process(int target, int[] nums, int i) {
        if (i == -1) return true;

        for (int j = 0; j < kids.length; j++) {
            if (nums[i] + kids[j] <= target) {
                if (j != 0 && kids[j] == kids[j - 1]) continue;
                kids[j] += nums[i];
                if (process(target, nums, i - 1)) return true;
                kids[j] -= nums[i];
            }
        }
        return false;
    }
}
